import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description: 填充每个节点的下一个右侧节点指针
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，
 * 每个父节点都有两个子节点。二叉树定义如下：
 * @Date:Create in 10:17  2022/7/20
 */
public class connect0116 {

    //层序遍历
    public static Node connect1(Node root) {
        if (root == null) return root;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            int len = que.size();
            for (int i = 0; i < len; i++) {
                Node node = que.poll();
                if (i < len - 1) node.next = que.peek();
                if (node.left != null) {
                    que.add(node.left);
                }
                if (node.right != null) {
                    que.add(node.right);
                }
            }
        }
        return root;

    }

    //使用已建立的next 指针
    /*
    1、 第一种情况两个子节点属于同一个父节点，
        因此直接通过父节点建立两个子节点的next指针即可。
        node.left.next = node.right
    2、 第二种情况是连接不同父节点之间子节点的情况。
        更具体地说，连接的是第一个父节点的右孩子和第二父节点的左孩子。
        由于已经在父节点这一层建立了next 指针，
        因此可以直接通过第一个父节点的next 指针找到第二个父节点，
        然后在它们的孩子之间建立连接。
        node.right.next = node.next.left
     */
    public static Node connect2(Node root) {
        if(root == null) return root;
        Node leftmost = root;
        while(leftmost.left!=null){
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftmost;
            while(head!=null){
                head.left.next = head.right;
                if(head.next!=null){
                    head.right.next = head.next.left;
                }
                head = head.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
